package com.leetcode.partition2;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/20 15:35
 */
public class LC152乘积最大子数组 {

    public static int maxProduct(int[] nums) {
        return dynamicProgramming(nums);
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        System.out.println(maxProduct(nums));
    }

    private static int dynamicProgramming(int[] nums) {
        //dp[0][i]：nums[0, i]乘积最大子数组    dp[1][i]：nums[0, i]乘积最小子数组
        int[][] dp = new int[2][nums.length];
        dp[0][0] = dp[1][0] = nums[0];
        int answer = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[0][i] = Math.min(Math.min(dp[1][i - 1] * nums[i], dp[0][i - 1] * nums[i]), nums[i]);
            dp[1][i] = Math.max(Math.max(dp[1][i - 1] * nums[i], dp[0][i - 1] * nums[i]), nums[i]);
            answer = Math.max(answer, dp[1][i]);
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return answer;
    }
}
